Theory Lunch

Cosystolic expansion of Chevalley coset complex HDXs

Noah Singer

January 22, 2025 (GHC 8102)

Abstract: Cosystolic expansion is a generalization of vertex expansion in graphs to "higher dimensions" (i.e., to simplicial complexes). Sparse, efficiently-constructible cosystolic expanders have powered recent breakthroughs in quantum coding and local testability, but these constructions are hard to come by. In this talk, I will present recent joint work with Ryan O'Donnell which analyzes the cosystolic expansion of a certain algebraically-defined complex, called a "B-type Chevalley coset complex", constructed by O’Donnell & Pratt. Our analysis builds on a recent, simpler analysis of a related "A-type complex" due to Kaufman & Oppenheim. These complexes have the advantage that, unlike earlier known complexes due to Lubotzky, Samuels, & Vishne, analyzing their expansion does NOT require any deep mathematical tools. I will define all relevant notions, so no prior knowledge of expansion or algebra is required.